package zcjq.d912d;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class P2 {
    public static void main(String[] args) {
        /*Scanner scanner = new Scanner(System.in);
        int n = Integer.parseInt(scanner.nextLine().trim());
        String str = scanner.nextLine().trim();
        int[] max = new int[]{0};
        bt(str.toCharArray(), 0, new ArrayList<>(), max);*/

        String[] cases = new String[]{
                "0101", "0011", "001011", "0231", "202313",
                "010101", "000111", "021331s"
        };
        for (String s : cases) {
            System.out.println(s + "\t" + dp(s.toCharArray()));
        }
    }


    private static int dp(char[] nums) {
        int len = nums.length;
        int max = 0;
        int[] dp = new int[len];
        for (int i = 0; i < len; i++) {
            char c = nums[i];
            if (c == '0' || c == '2') {
                continue;
            } else {
                for (int j = i - 1; j >= 0; j--) {
                    if (c - nums[j] == 1) {
                        nums[j] = '*';
                        nums[i] = '*';
                        break;
                    }
                }
            }
        }
        int total = 0;
        for (char c : nums) {
            if (c == '*') {
                total++;
            }
        }
        return total;
    }

     /*int maxLen = 0;
        int total = 0;
        Stack<Character> stack = new Stack<>();
        for (char c : str.toCharArray()) {
            char tmp = ' ';
            switch (c) {
                case '0':
                case '2':
                    stack.push(c);
                    break;
                case '1':
                    if (stack.size() == 0) break;
                    while ((tmp = stack.pop()) != '0') {
                    }
                    if (tmp == '0') {
                        total += 2;
                    } else {
                        stack.clear();
                        maxLen = Math.max(total, maxLen);
                        total = 0;
                    }
                    break;
                case '3':
                    if (stack.size() == 0) break;
                    //寻找2
                    while ((tmp = stack.pop()) != '2') {
                    }
                    if (tmp == '2') {
                        total += 2;
                    } else {
                        stack.clear();
                        maxLen = Math.max(total, maxLen);
                        total = 0;
                    }
            }
        }
        System.out.println(Math.max(total, maxLen));*/
}
